package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 1145. 二叉树着色游戏
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/16 23:09
 */
public class BtreeGameWinningMove {

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        TreeNode treeNode = find2(root, x);
        int a = find(treeNode.left);
        int b = find(treeNode.right);
        int c = n - a - b - 1;
        int max = Math.max(a, Math.max(b, c));
        return max > (n >> 1);
    }

    private TreeNode find2(TreeNode root, int x) {
        if (root == null) {
            return null;
        }
        if (root.val == x) {
            return root;
        }
        TreeNode treeNode = find2(root.left, x);
        if (treeNode != null) {
            return treeNode;
        }
        return find2(root.right, x);
    }

    private int find(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return find(node.left) + find(node.right) + 1;
    }

}
